package arithmetic1.kruskal;

import java.util.*;

/*
    kruskal算法和prim算法是两个求图的最小连通子图的算法
        kruskal算法思想:
            将所有的路径按权值从小到大排序，每次从其中选择最小的一个边加入，并且选择的边之间不能形成回路
        判断是否形成回路的方法:
            将加入的连按照从小到大排序，所有加入点的终点都为最大的那个点，如果再想加入一条边，那么这条边的
            两个顶点的的终点不能都指向同一个终点
 */
public class Kruskal {
    //用kruskal算法求解最小生成树
    public static void kruskal(Graph graph){
        //将路径取值存放在集合里面,自动排好序
        Set<Side> sides1=new TreeSet<>();
        for(int i=0;i<graph.matrix.length;i++){
            for(int j=0;j<graph.matrix[i].length;j++){
                if(graph.matrix[i][j]!=0){
                    sides1.add(new Side(i,j,graph.matrix[i][j]));
                }
            }
        }
        //存放选择的边的集合
        Set<Side> sides2=new TreeSet<>();
        //从
        sides2.add(new Side(2,3,3));
        sides2.add(new Side(3,4,4));
        sides2.add(new Side(4,5,2));
        isLoop(sides2,new Side(),7 );


//        for(Side side:sides1){
//            System.out.println(side);
//        }
    }

    //将选择的边和之前加入的所有边比较，是否形成回路
    //sides是已经加入的边的集合,side是待加入的边
    public static boolean isLoop(Set<Side> sides,Side side,int peak){
        //定义一个二维数组来存储每一个顶点的终点
        int ends[][]=new int[2][peak];
        //初始化ends
        for(int i=0;i<2;i++){
            for(int j=0;j<peak;j++){
                if(i==0){
                    ends[i][j]=j;
                }else{
                    ends[i][j]=-1;
                }
            }
        }
        for(int i=0;i<peak;i++){    //找出每个顶点的终点

        }

        for(int arr[]:ends){
            System.out.println(Arrays.toString(arr));
        }
        return false;
    }

//    //求一个顶点的终点
//    public static int end(Set<Side> sides,int i){
//        int end=-1;
//        while (){
//            for(Side side:sides){
//                if(i==side.start){
//                    i=side.end;
//                    end=side.end;
//                }
//            }
//        }
//        return 0;
//    }
}

class Graph{
    //图的顶点个数
    int peak;

    //存储图的邻接矩阵
    int matrix[][];

    //存储图的顶点
    String nodes[];

    public Graph(int peak) {
        this.peak = peak;
        nodes=new String[peak];
        matrix=new int[peak][peak];
    }

    //设置图的邻接矩阵
    public void setMatrix(int[][] matrix) {
        this.matrix = matrix;
    }

    //设置图的顶点符号
    public void setNodes(String nodes[]){
        this.nodes=nodes;
    }

    //显示图的邻接矩阵
    public void show(){
        for(int[] arr:matrix){
            for(int value:arr){
                System.out.printf("%5d  ",value);
            }
            System.out.println();
        }
    }
}

class Side implements Comparable<Side>{
    int start;  //边的起点
    int end;    //边的终点
    int value;  //边的权值

    public Side() {
    }

    public Side(int start, int end, int value) {
        this.start = start;
        this.end = end;
        this.value = value;
    }

    @Override
    public String toString() {
        return "Side{" +
                "start=" + start +
                ", end=" + end +
                ", value=" + value +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Side side = (Side) o;
        return (start == side.start &&
                end == side.end &&
                value == side.value)
                || (start == side.end &&
                end == side.start &&
                value == side.value) ;
    }

    @Override
    public int hashCode() {
        return Objects.hash(start, end, value);
    }

    //按照权值升序
    @Override
    public int compareTo(Side o) {
        return this.value-o.value;
    }
}

class Test{
    public static void main(String[] args) {
        Graph graph=new Graph(7);
        String nodes[]={"A","B","C","D","E","F","G"};
        int matrix[][]={
                {0,12,0,0,0,16,14},
                {12,0,10,0,0,7,0},
                {0,10,0,3,5,6,0},
                {0,0,3,0,4,0,0},
                {0,0,5,4,0,2,8},
                {16,7,6,0,2,0,9},
                {14,0,0,0,8,9,0}
        };
        graph.setMatrix(matrix);
        graph.setNodes(nodes);
//        arithmetic1.graph.show();
        Kruskal.kruskal(graph);
//        Kruskal.isLoop(new TreeSet<Side>(), new Side(),7);
    }
}
